package com.qch.edu.lagou.algorithm.list;

/**
 * @Author qch
 * @Date 2021/7/23
 * 判断链表是否有环
 * 比如：一快一慢两个运动员，如果在直道赛跑，不存在追击相遇问题；如果是在环道赛跑，快的绕了一
 * 圈肯定可以追上慢的。
 *
 * 思路：1. 定义快慢两个指针：slow=head; fast=head.next;
 * 2. 遍历链表：快指针步长为2：fast=fast.next.next; 
 * 慢指针步长为1：slow=slow.next;
 * 3. 当且仅当快慢指针重合(slow==fast)，有环，返回true
 * 4. 快指针为null，或其next指向null，没有环，返回false，操作结束
 */
public class RingList {
    /**
     * 判断链表是否有环
     * @param head
     * @return
     */
    public static boolean isRing(Node head){
        if (head==null)
        {
            return false;
        }
        //定义快慢指针
        Node slow=head;
        Node fast=head.next;
        while (fast!=null&&fast.next!=null)
        {
            if(slow==fast){
                return true;
            }
            fast=fast.next.next;//步长为2
            slow=slow.next;//步长为1
        }
        return false;
    }

    public static void main(String[] args) {
        Node n1 = new Node(1, "张飞");
        Node n2 = new Node(2, "关羽");
        Node n3 = new Node(3, "赵云");
        Node n4 = new Node(4, "黄忠");
        Node n5 = new Node(5, "马超");
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n1;
        //n5.next = null;
        System.out.println(isRing(n1));
    }
}
